1. Field of the Invention
The present invention relates to the field of content addressable memories, associative storage, parallel-search storage or the like.
2. Description of the Related Art
FIG. 1 presents a cascaded content addressable memory (CAM) system including a plurality of CAM chips such as CAM 1, CAM 2, CAM 3 through CAM N. CAMs are used in computer data processing where it is desirable to identify the location of the data stored in the memory by specifying part or all of its contents. When a match is found in a CAM chip, the CAM chip sends an output to its match line (such as match/ 1, match/ 2, etc.) indicating that a match is found in that CAM chip. The match output stage of a CAM chip is shown in FIG. 2 in more detail.
FIG. 2 shows a plurality of output stages (80-81) of CAM chips 40-41. Each CAM chip's output stage utilizes an "open drain" implementation for its match/ output, allowing the match/ outputs of a system of cascaded CAM chips to be directly connected. A match/output stage of a CAM chip includes an N-channel MOSFET, a pull-down input signal and a match/ line. For example, CAM chip 40 has (i) an N-channel MOSFET 80, (ii) a pd 1 coupled to the gate of N-channel MOSFET 80 and (iii) a match/ 1 (50) coupled to the drain of N-channel MOSFET 80 and to a system match/ line 63. If any CAM chip has a match, that CAM chip's pd signal becomes a logic high, turning on the corresponding N-channel MOSFET and pulling down system match/ line 63. If none of the CAM chips have a match, then all of the CAM chip's pd signals become a logic low, and system match/ line 63 is pulled high by an external pull-up resistor 60. Therefore, a logic low on system match/ line 63 indicates that one or more CAM chips have a match, and a logic high on system match/ line 63 indicates that no CAM chip in the cascade of CAMs has a match.
The "open drain" implementation shown in FIG. 2 requires a trade-off between the speed of the system and the size of the system due to the RC delay incurred in pulling up system match/ line 63. The RC delay results from external pull-up resistor 60 and the inherent capacitance of the outputs and the connections of the outputs.
A match valid time, tMV 72, and a match recovery time, tMR 71, are shown in FIG. 3 of the timing diagram. Time period tMV 72 includes a time interval between the time when the clock goes low in the third clock cycle of the match instruction and the time when system match/ line 63 is pulled low by one or more of CAM chips 40-41. Time period tMR 71 is a time interval between the time when the clock goes low in the first clock cycle of the match instruction and the time when the system match/ line 63 is pulled high by external pull-up resistor 60. If tMR 71 is greater than tMV 72 plus two clock cycles, then tMR 71 limits the speed of the cascaded CAM system.
The output voltage as it is pulled up by external resistor 60 is given by the equation: EQU Vout=Vol+([Vcc-Vol]* {1-(exp [-t/(R*Ctot)])}), (1)
where R is the resistance value of external pull-up resistor 60 and Ctot is the total capacitance on system match/ line 63. Ctot is the number of CAM chips in the cascaded system multiplied by the sum of the output capacitance and the board routing capacitance for each chip.
The minimum value of R is determined from the equation: EQU R=(Vcc -Vol)/Iol (2)
The minimum match recovery time, tMR 71 , is the time t when Vout reaches Voh.
Typical specifications for the parameters that affect the rise time of the output are listed below:
Vcc=5.0 V; PA1 Voh=2.4 V; PA1 Vol=0.5 V; PA1 Iol=30 mA; EQU Cout=15 pF (10 pF for an output and 5 pF for the board routing for an output). (3)
With Cout being 15 pF, Ctot=(n * 15 pF), where n is the number of CAM chips in the cascaded system.
From equations (2) and (3) , EQU R=[(5.0 V-0.5 V) / 30 mA]=150 Ohms (4)
If n is the number of CAM chips in the cascaded system, substituting equations (3) and (4) into equation (1) to find the minimum tMR gives EQU 2.4 V=0.5 V+(4.5 V *{1-(exp[-tMR/(150 Ohms * n * 15 pF) ])})
Simplifying the above equation further yields tMR=[(n * 2.25 ns) * (ln (26/45))], and it finally yields tMR=n * (1.23 ns).
When tMV 72 is 14 ns, and a clock cycle is 20 ns, only 43 CAM chips can be cascaded before tMR begins to limit the speed of the cascaded system. Any system of CAM chips requiring more than 43 chips is then limited by the "open drain" implementation of the system match/ output.
FIG. 6 shows the states, during 4 clock cycles, of a pd signal and system match/ line 63 (in the comment field of FIG. 6). During a clock period of 1A, the pd signal contains the previous match signal, and system match/ line 63 is active. During the period of 1B, 2A, 2B and 3A, the pd signal is a logic low, so system match/ line 63 is in a tri-state. Depending on how long it takes to pull up system match/ line 63 to a logic high by R 60, this period may consist of more clock cycles. During a period including 3B, 4A and 4B, the pd signal receives a new match signal while system match/ line 63 is active.
The present invention incorporates a precharge circuit so that tMR does not limit the number of CAM chips that can be utilized in a CAM system and the speed of the cascaded CAM system.